package chapter01.problem09;

import java.util.Stack;

public class Problem09 {

	public static int getMaxSubMatrix(int[][] matrix){
		int rowNum = matrix.length;
		if(rowNum <= 0 )
			return 0;
		int columnNum = matrix[0].length;
		int max = 0;
		int [] high = new int[columnNum];
		for(int i= 0; i < rowNum; ++i){
			int a = getMax(matrix[i],high,columnNum);
			if(max < a)
				max = a;
		}
		return max;
	}
	
	private static int getMax(int[] array, int[] high, int columnNum) {
		for( int i = 0; i < columnNum;++i){
			high[i]=array[i]==0?0:high[i]+1;
		}
		Stack<Integer> stack = new Stack<Integer>();
		int[] left = new int[columnNum];
		int[] right = new int[columnNum];
		for(int i = 0; i < columnNum; ++i){
			while(!stack.isEmpty()){
				if(high[stack.peek()] < high[i]){
					break;
				}else{
					int top = stack.pop();
					if(high[top] > high[i]){
						right[top] =i-1;
						left[top] = stack.isEmpty()?0:stack.peek()+1;
					}else{
						right[top] = 0;
						left[top] = 0;
					}
				}
			}
			stack.push(i);
		}
		while(!stack.isEmpty()){
			int top = stack.pop();
			right[top] = columnNum - 1; 
			left[top] = stack.isEmpty()?0:stack.peek()+1; 
		}
		int max=0;
		for(int i = 0; i < columnNum; ++i){
			int a = (right[i]-left[i]+1)*high[i];
			if(max < a)
				max = a;
		}
		return max;
	}

	public static void main(String[] args) {
		int[][] a = {{1,0,1,},{1,1,1},{1,1,1,0}};
		int max = Problem09.getMaxSubMatrix(a);
		System.out.println(max);
	}
}
